package com.sheng.leetcode.year2022.month08.day13;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/08/25
 *
 * 769. 最多能完成排序的块
 *
 * 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
 * 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
 * 返回数组能分成的最多块数量。
 *
 * 示例 1:
 * 输入: arr = [4,3,2,1,0]
 * 输出: 1
 * 解释:
 * 将数组分成2块或者更多块，都无法得到所需的结果。
 * 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
 *
 * 示例 2:
 * 输入: arr = [1,0,2,3,4]
 * 输出: 4
 * 解释:
 * 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
 * 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
 *
 * 提示:
 *
 * n == arr.length
 * 1 <= n <= 10
 * 0 <= arr[i] < n
 * arr 中每个元素都 不同
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0769 {

    @Test
    public void test01() {
//        int[] arr = {4,3,2,1,0};
        int[] arr = {1,0,2,3,4};
        System.out.println(new Solution1().maxChunksToSorted(arr));
    }
}
class Solution1 {
    public int maxChunksToSorted(int[] arr) {
        int length = arr.length;
        //将原数组分割成多块，对每块进行排序后连接起来，和原数组直接排序得到的结果一致
        int[] clone = arr.clone();
        Arrays.sort(clone);
        int index = 0;
        //代表分割成的数组的块数
        int count = 0;
        boolean flag = false;
        for (int i = 0; i < length; i++) {
            //如果经过最小值，则可以进行切分数组判断
            if (arr[i] == index) {
                flag = true;
            }
            if (flag) {
                int[] ints = Arrays.copyOf(arr, i + 1);
                Arrays.sort(ints);
                //切分后的数组如果满足条件，则可以进行切分
                //int[] ints1 = Arrays.copyOf(clone, i + 1);
                //判断切分后的数组和排序后的原数组切分后是否一致也可以实现：Arrays.equals(ints, ints1)
                if (judge(ints)) {
                    index = ints[ints.length - 1] + 1;
                    count++;
                    flag = false;
                }
            }
        }
        return count;
    }

    /**
     * 判断数组的后一个元素是否总比前一个元素大1
     *
     * @param ints 数组
     * @return boolean
     */
    public boolean judge(int[] ints) {
        for (int i = 0; i < ints.length - 1; i++) {
            if (ints[i + 1] - ints[i] != 1) {
                return false;
            }
        }
        return true;
    }
}

//class Solution {
//    public int maxChunksToSorted(int[] arr) {
//        int ans = 0, max = 0;
//        for (int i = 0; i < arr.length; ++i) {
//            max = Math.max(max, arr[i]);
//            if (max == i) ans++;
//        }
//        return ans;
//    }
//}
//
//作者：LeetCode
//链接：https://leetcode.cn/problems/max-chunks-to-make-sorted/solution/zui-duo-neng-wan-cheng-pai-xu-de-kuai-i-by-leetcod/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
